package com.offer;


import com.bean.TreeNode;
import com.utils.TreeUtils;

public class Test68_2 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root.val == p.val || root.val == q.val) {
            return root;
        }

        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);

        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);

        if (leftNode != null && rightNode != null) {
            return root;
        }

        if (rightNode != null) {
            return rightNode;
        }

        if (leftNode != null) {
            return leftNode;
        }

        return null;
    }

    public static void main(String[] args) {
//        TreeNode node = TreeUtils.buildTree("6,2,8,0,4,7,9,null,null,3,5");
        TreeNode node = TreeUtils.buildTree("3,5,1,6,2,0,8,null,null,7,4");
        TreeUtils.showTree(node);

        Test68_2 test = new Test68_2();
        System.out.println(test.lowestCommonAncestor(node, new TreeNode(5), new TreeNode(4)).val);
    }

}
